#https://leetcode.cn/problems/house-robber/submissions/560802819/

class Solution {
public:
    int rob(vector<int>& nums) {
        // 如果数组长度小于2，直接返回唯一的元素
        if(nums.size() < 2) return nums[0];
        // 初始化动态规划表，ew[i] 表示偷到第 i 房子为止能获得的最大金额
        vector<int> ew(nums.size()+1,0);
        ew[1] = max(nums[0], nums[1]);
        ew[0] = nums[0];
        
        for(int i = 2; i < nums.size(); i++) {
            ew[i] = max(ew[i-1], ew[i-2] + nums[i]);
        }
        // 返回最后一间房子为止的最大收益
        return ew[nums.size()-1];
    }
};